package main

func main() {
	// [面试题 02.07. 链表相交](https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/)
	// [142. 环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/)
	// [242. 有效的字母异位词](https://leetcode.cn/problems/valid-anagram/)
	// [349. 两个数组的交集](https://leetcode.cn/problems/intersection-of-two-arrays/)
	// [202. 快乐数](https://leetcode.cn/problems/happy-number/)
}

// 02.07
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	curA, curB := headA, headB
	countA, countB := 0, 0
	for curA != nil {
		countA++
		curA = curA.Next
	}
	for curB != nil {
		countB++
		curB = curB.Next
	}
	if countB > countA {
		headA, headB = headB, headA
		countA, countB = countB, countA
	}
	curA, curB = headA, headB
	diff := countA - countB
	for diff > 0 {
		curA = curA.Next
		diff--
	}
	for curA != nil && curB != nil {
		if curA == curB {
			return curA
		}
		curA = curA.Next
		curB = curB.Next
	}
	return nil
}

// 142
func detectCycle(head *ListNode) *ListNode {
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
		if fast == slow {
			for head != slow {
				slow = slow.Next
				head = head.Next
			}
			return slow
		}
	}
	return nil
}

// 242
func isAnagram(s string, t string) bool {
	bytemap := make(map[byte]int)
	for i := range s {
		ch := s[i]
		bytemap[ch]++
	}
	for i := range t {
		ch := t[i]
		bytemap[ch]--
		if bytemap[ch] == 0 {
			delete(bytemap, ch)
		}
	}
	return len(bytemap) == 0
}

// 349
func intersection(nums1 []int, nums2 []int) []int {
	mp1, mp2 := map[int]struct{}{}, map[int]struct{}{}
	for _, v := range nums1 {
		mp1[v] = struct{}{}
	}
	for _, v := range nums2 {
		mp2[v] = struct{}{}
	}
	ans := make([]int, 0)
	for k1 := range mp1 {
		_, ok := mp2[k1]
		if ok {
			ans = append(ans, k1)
		}
	}
	return ans
}

// 202
func isHappy(n int) bool {
	fast, slow := cal(n), n
	for fast != slow {
		fast = cal(cal(fast))
		slow = cal(slow)
	}
	return slow == 1
}

func cal(n int) int {
	sum := 0
	for n > 0 {
		tmp := n % 10
		sum += tmp * tmp
		n /= 10
	}
	return sum
}
